package 中等.搜索.记忆化搜索;

/**
 * 爱丽丝和鲍勃继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗
 * 石子 piles[i]。游戏以谁手中的石子最多来决出胜负。
 * 爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。
 * 在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 
 * 1 <= X <= 2M。然后，令 M = max(M, X)。
 * 游戏一直持续到所有石子都被拿走。
 * 假设爱丽丝和鲍勃都发挥出最佳水平，返回爱丽丝可以得到的最大数量的石头。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/stone-game-ii
 */
public class 石子游戏II_1140 {

    public static void main(String[] args) {

        System.out.println(stoneGameII(new int[]{2, 7, 9, 4, 4}));

    }

    private static int[] prefixSum;
    private static Integer[][] record;

    /**
     * 前缀和+记忆化搜索
     */
    public static int stoneGameII(int[] piles) {
        // 多建一个位置，prefixSum[i] 表示前i个数的和是多少
        prefixSum = new int[piles.length + 1];
        for (int i = 0; i < piles.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + piles[i];
        }

        record = new Integer[piles.length][piles.length / 2 + 1];

        return dfs(0, 1);
    }

    /**
     * 表示从索引 idx 开始，往后取最多 2M 个数，使得当前玩家获得最大数量的石子是多少
     * 1，如果可以取走剩下的全部石子堆，直接全部取走
     * 2，如果不能取走全部石子堆，那么当前玩家可能取走的石子数量
     * 等于 剩下的全部石子数 - 下一位玩家可以取走的石子数量
     */
    private static int dfs(int idx, int M) {
        if (prefixSum.length - idx <= 2 * M) {
            return prefixSum[prefixSum.length - 1] - prefixSum[idx];
        }

        if (record[idx][M] != null) {
            return record[idx][M];
        }

        int maxSum = 0;
        for (int X = 1; X <= 2 * M; X++) {
            maxSum = Math.max(maxSum, prefixSum[prefixSum.length - 1] - prefixSum[idx]
                    - dfs(idx + X, Math.max(M, X)));
        }
        return record[idx][M] = maxSum;
    }

}
